\chapter{队列}

\section{队列}

\subsection{队列（Queue）}

队列是一种运算受限的线性数据结构，不同于栈的先进后出（FILO），队列中的元素只能先进先出（FIFO, First In First Out）。\\

队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。队列只允许在队尾进行入队（enqueue），在队头进行出队（dequeue）。\\

与栈类似，队列既可以用数组来实现，也可以用链表来实现。其中用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置。\\

\subsection{入列（enqueue）}

入队就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。入队操作的时间复杂度是$ O(1) $。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\fill[green!20] (5.1,.35) rectangle (-.6,-.35);
		\draw[green,thick] (-.6,.35) -- (5.1,.35) |- (-.6,-.35);
		\foreach \i/\name in {0/A,1/B,2/C}
		\node[queue element] (\name) at (1.5*\i,0) {\name};
		\draw[<-] ([yshift=.2cm]C.north) -- ++ (0,.5) node[above] {rear};
		\draw[<-] ([yshift=.2cm]A.north) -- ++ (0,.5) node[above] {front};
		\path (6,0) node[right] {before};
		\node[queue element] (D) at (6,1) {D};
		\draw[<-,very thick] (4.7,0) to[out=0,in=180] (D.south);

		\scope[yshift=-3cm]
		\fill[green!20] (5.1,.35) rectangle (-.6,-.35);
		\draw[green,thick] (-.6,.35) -- (5.1,.35) |- (-.6,-.35);
		\foreach \i/\name in {0/A,1/B,2/C,3/D}
		\node[queue element] (\name) at (1.5*\i,0) {\name};
		\draw[<-] ([yshift=.2cm]D.north) -- ++ (0,.5) node[above] {rear};
		\draw[<-] ([yshift=.2cm]A.north) -- ++ (0,.5) node[above] {front};
		\path (6,0) node[right] {after};
		\endscope
	\end{tikzpicture}
	\caption{入队}
\end{figure}

\vspace{0.5cm}

\subsection{出队（dequeue）}

出队就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将成为新的队头。出队操作的时间复杂度是$ O(1) $。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\fill[green!20] (5.1,.35) rectangle (-.6,-.35);
		\draw[green,thick] (-.6,.35) -- (5.1,.35) |- (-.6,-.35);
		\foreach \i/\name in {0/A,1/B,2/C,3/D}
		\node[queue element] (\name) at (1.5*\i,0) {\name};
		\draw[<-] ([yshift=.2cm]D.north) -- ++ (0,.5) node[above] {rear};
		\draw[<-] ([yshift=.2cm]A.north) -- ++ (0,.5) node[above] {front};
		\draw[->,very thick] (-.7,0) to[out=180,in=90] ++ (-1,-1);
		\path (6,0) node[right] {before};

		\scope[yshift=-3cm]
		\fill[green!20] (5.1,.35) rectangle (-.6,-.35);
		\draw[green,thick] (-.6,.35) -- (5.1,.35) |- (-.6,-.35);
		\foreach \i/\name in {1/B,2/C,3/D}
		\node[queue element] (\name) at (1.5*\i,0) {\name};
		\draw[<-] ([yshift=.2cm]D.north) -- ++ (0,.5) node[above] {rear};
		\draw[<-] ([yshift=.2cm]B.north) -- ++ (0,.5) node[above] {front};
		\path (6,0) node[right] {after};
		\endscope
	\end{tikzpicture}
	\caption{出队}
\end{figure}

\vspace{0.5cm}

\subsection{循环队列（Circular Queue）}

如果不断出队，队头左边的空间就失去了作用，那队列的容量就会变得越来越小。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\fill[green!20] (8.1,.35) rectangle (-.6,-.35);
		\draw[green,thick] (-.6,.35) -- (8.1,.35) |- (-.6,-.35);
		\foreach \i/\name in {0/A,1/B,2/C,3/D,4/E,5/F}
		\node[queue element] (\name) at (1.5*\i,0) {\name};
		\draw[<-] ([yshift=.2cm]F.north) -- ++ (0,.5) node[above] {rear};
		\draw[<-] ([yshift=.2cm]D.north) -- ++ (0,.5) node[above] {front};
		\draw[->,very thick] (-.7,0) to[out=180,in=90] ++ (-1,-1);

		\draw[-, red] (-0.5,0.5) -- (0.5,-0.5);
		\draw[-, red] (1,0.5) -- (2,-0.5);
		\draw[-, red] (2.5,0.5) -- (3.5,-0.5);
	\end{tikzpicture}
	\caption{队列存在的问题}
\end{figure}

用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。为充分利用空间，克服假溢出的现象，在数组不做扩容的情况下，将队列想象为一个首尾相接的圆环，可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。这样一来整个队列的元素就循环起来了。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[>=latex,font=\sffamily,semithick,scale=1.75]
		\fill [green!25] (0,0) -- (67.5:1) arc [end angle=-22.5, start angle=67.5, radius=1] -- cycle;
		\draw [thick] (0,0) circle (1);
		\foreach \angle in {90,67.5,...,-67.5}
		\draw (\angle:1) -- (\angle-180:1);
		\node [circle,thick,fill=white,draw=black,align=center,minimum size=3cm] at (0,0) {};
		\draw [<-] (56.25:1) -- (56.25:1.25) -- +(.333,0)
		node [right,inner xsep=.333cm] (front) {front};
		\draw [<-] (-33.75:1) -- (-33.75:1.25) -- +(.333,0)
		node [right,inner xsep=.333cm] (rear) {rear};
	\end{tikzpicture}
	\caption{循环队列}
\end{figure}

在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。队头和队尾互相追赶，这个追赶的过程就是入队的出队的过程。\\

如果队尾追上队头说明队列满了，如果队头追上队尾说明队列为空。循环队列并非真正地把数组弯曲，利用求余操作就能使队头和队尾指针不会跑出数组的范围，逻辑上实现了弯曲的效果。\\

假设数组的最大容量为MAX：

\begin{itemize}
	\item 入队时队尾指针后移：(rear + 1) \% MAX

	\item 出队时队头指针后移：(front + 1) \% MAX

	\item 判断队满：(rear + 1) \% MAX == front

	\item 判断队空：front == rear
\end{itemize}

需要注意的是，队尾指针指向的位置永远空出一位，所以队列最大容量比数组长度小1。\\

\mybox{入队}

\begin{lstlisting}[language=C]
queue_t *queue_enqueue(queue_t *quque, T elem) {
	queue->data[queue->rear] = elem;
	queue->rear = (queue->rear + 1) % queue->max;
	return queue;
}
\end{lstlisting}

\vspace{0.5cm}

\mybox{出队}

\begin{lstlisting}[language=C]
T queue_enqueue(queue_t *queue) {
	T elem = queue->data[queue->front];
	queue->front = (queue->front + 1) % queue->max;
	return elem;
}
\end{lstlisting}

\newpage

\section{双端队列}

\subsection{双端队列（Deque, Double Ended Queue）}

双端队列是一种同时具有队列和栈的性质的数据结构，双端队列可以从其两端插入和删除元素。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\fill[green!20] (6.6,.35) rectangle (-.6,-.35);
		\draw[green,thick] (-.6,.35) -- (6.6,.35) |- (-.6,-.35);
		\foreach \i/\name in {0/A,1/B,2/C,3/D,4/E}
		\node[queue element] (\name) at (1.5*\i,0) {\name};
		\draw[<-] ([yshift=.2cm]E.north) -- ++ (0,.5) node[above] {rear};
		\draw[<-] ([yshift=.2cm]A.north) -- ++ (0,.5) node[above] {front};

		\draw[->,very thick] (-0.9,0.3) -- (-1.7,0.3);
		\draw[->,very thick] (-1.7,-0.3) --  (-0.9,-0.3);

		\draw[<-,very thick] (7,0.3) -- (7.8,0.3);
		\draw[<-,very thick] (7.8,-0.3) -- (7,-0.3);
	\end{tikzpicture}
	\caption{双端队列}
\end{figure}

\mybox{双端队列}

\begin{lstlisting}[language=Python]
class Deque:
    def __init__(self):
        self.__data = []
    
    def is_empty(self):
        return self.__data == []
    
    def __len__(self):
        return len(self.__data)
    
    def push_front(self, elem):
        self.__data.insert(0, elem)
    
    def push_back(self, elem):
        self.__data.append(elem)
    
    def pop_front(self):
        return self.__data.pop(0)
    
    def pop_back(self):
        return self.__data.pop()
    
    def front(self):
        return self.__data[0]
    
    def back(self):
        return self.__data[-1]
\end{lstlisting}

\newpage